package org.example.myleet.p475;

import java.util.Arrays;

public class Solution {

    /**
     * 官方思路，双指针法。关键的指导思想：house使用的heater不是前一个就是后一个
     * houseI指针和heaterI指针，其中heaterI指针需要保持heaters[heaterI]的值必须大于houses[houseI]，
     * 这样总可以形成heaters[heaterI - 1] <= houses[houseI] < heaters[heaterI]的局面，
     * 此时就可以找到距离houses[houseI]最近的heater，并以此更新最小半径的需求
     */
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(houses);
        Arrays.sort(heaters);
        int houseI = 0, heaterI = 0;
        int maxRadius = 0;
        while (houseI < houses.length) {
            if (houses[houseI] <= heaters[0]) {
                maxRadius = Math.max(maxRadius, heaters[0] - houses[houseI]);
            } else if (houses[houseI] >= heaters[heaters.length - 1]) {
                maxRadius = Math.max(maxRadius, houses[houseI] - heaters[heaters.length - 1]);
            } else {
                while (heaterI < heaters.length && heaters[heaterI] < houses[houseI]) {
                    ++heaterI;
                }
                maxRadius = Math.max(maxRadius, Math.min(heaters[heaterI] - houses[houseI], houses[houseI] - heaters[heaterI - 1]));
            }
            ++houseI;
        }
        return maxRadius;
    }

    /**
     * 二分法思路，对heaters排序，针对每个house，在heaters中用二分法快速找到距离最近的heater，并以此更新最小半径的需求
     */
//    public int findRadius(int[] houses, int[] heaters) {
//        Arrays.sort(heaters);
//        int maxRadius = 0;
//        for (int i = 0; i < houses.length; ++i) {
//            if (houses[i] <= heaters[0]) {
//                maxRadius = Math.max(maxRadius, heaters[0] - houses[i]);
//            } else if (houses[i] >= heaters[heaters.length - 1]) {
//                maxRadius = Math.max(maxRadius, houses[i] - heaters[heaters.length - 1]);
//            } else {
//                int l = 0, r = heaters.length - 1, m;
//                while (l < r) {
//                    m = (r + l) >> 1;
//                    if (heaters[m] < houses[i]) {
//                        l = m + 1;
//                    } else {
//                        r = m;
//                    }
//                }
//                maxRadius = Math.max(maxRadius, Math.min(houses[i] - heaters[l - 1], heaters[l] - houses[i]));
//            }
//        }
//        return maxRadius;
//    }
}
